Graphe de voisinage relatif

En géométrie algorithmique, le graphe de voisinage relatif (en anglais relative neighborhood graph, souvent abrégé RNG) est un graphe non orienté qui connecte un ensemble de points dans un espace euclidien. Plus précisément, il connecte deux points ${\displaystyle p}$ et ${\displaystyle q}$ si et seulement s'il n'existe pas de troisième point ${\displaystyle r}$ qui soit plus proche de ${\displaystyle p}$ et de ${\displaystyle q}$ qu'ils ne le sont entre eux. Il est introduit en 1980 par Godfried Toussaint (en)^[1].